package minWindow

/**
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
*/
func minWindow(s string, t string) string {
	need := make(map[uint8]int)
	window := make(map[uint8]int)
	// 初始化need
	for i := 0; i < len(t); i++ {
		need[t[i]]++
	}
	//左指针，右指针，最短覆盖子串的长度，已经覆盖的字符个数，最短覆盖子串的起点坐标
	left, right, l, valid, start := 0, 0, 1000000, 0, 0

	for right < len(s) {
		//移入窗口内的字符
		inChar := s[right]
		// 判断子串中是否含有该字符
		if need[inChar] > 0 {
			window[inChar]++
			if window[inChar] == need[inChar] {
				valid++
			}
		}
		// 窗口右移
		right++

		//判断是否需要从窗口移除字符
		//移除到不再覆盖子串为止
		for valid == len(need) {
			// 更新最短覆盖子串长度
			if right-left < l {
				start = left
				l = right - left
			}
			outChar := s[left]
			// 窗口右移
			left++
			if need[outChar] > 0 {
				if window[outChar] == need[outChar] {
					valid--
				}
				window[outChar]--
			}
		}
	}
	if l == 1000000 {
		return ""
	}
	s2 := s[start : start+l]
	return s2

}
